1. Field
Embodiments of the invention relate to systems and methods for finding shortest paths in spatial networks.
2. Description of the Related Art
The trend towards smaller computing platforms and mobile devices, as well as the concomitant increase in their power, has led to an increasing interest in their use to facilitate the mobility of their owners. This has resulted in the development of a new component of the software industry known collectively as location-based services. Such location-based services can be used to continuously monitor ever-changing user positions as well as their destinations, and provide up-to-the-minute (second) information about their environment, as well as paths to their destinations. This is especially useful in an emergency response environment where destinations may change given the continuously changing conditions on the ground. The challenge in providing location information includes the fact that these paths are not simple to compute as it is desirable to take the shortest paths, and the total distance is computed along a network instead of “as the crow flies.”
In fact, changes may occur so quickly that there may not be enough time to compute exact answers and, therefore, many solutions resort to estimates (i.e., approximate answers) with some guarantee of optimality (i.e., within some tolerance e). Moreover, in these situations, there is a need to interact with a multitude of information sources such as road networks, building diagrams, service areas, etc. Increasingly, these information sources are stored in databases that must be accessible using a common interface (i.e., language), most often some variant of SQL.